/*
 * @LastEditTime: 2023-03-31 23:28:32
 * @Method: 
 * @Description: 
 */
package CodeTop;

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution143 {
    public void reorderList(ListNode head) {
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        ListNode middle = slow;
        ListNode pre = null;
        ListNode cur = middle.next;
        middle.next = null;
        while (cur != null) {
            ListNode t = cur.next;
            cur.next = pre;
            pre = cur;
            cur = t;
        }
        ListNode p1 = pre, p2 = head;
        while (p1 != null) {
            ListNode t = p1.next;
            p1.next = p2.next;
            p2.next = p1;
            p2 = p2.next.next;
            p1 = t;
        }
    }
}